package me.shan.data.structure;

/**
 * 描述：栈，先进后出 链表实现
 *
 * @author liuchuang
 * @date 2021/6/29 10:03
 */
public class LinkedListStack {

    protected Node<Integer> head = null;
    protected Node<Integer> tail = null;

    public void push(Integer value) {
        Node<Integer> node = new Node<>(value);
        if (head == null) {
            head = node;
        }
        if (tail != null) {
            tail.setNext(node);
        }
        tail = node;
    }

    public Integer pop() throws Exception {
        // 空栈
        if (tail == null) {
            throw new Exception("空栈无法使用pop指令");
        }
        // 栈中只有一个元素，head和tail重合
        if (head == tail) {
            Integer value = head.getValue();
            head = null;
            tail = null;
            return value;
        }
        // 将tail设置成前面一个
        Node<Integer> node = head;
        while (node.getNext() != tail) {
            node = node.getNext();
        }
        // 此时 node.next 指向的就是 tail 尾指针
        // 将tail设置成前面一个，并将next指针置空
        Integer value = tail.getValue();
        tail = node;
        tail.setNext(null);
        return value;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("{Stack: { ");
        if (head == null) {
            stringBuilder.append("null }}");
        } else {
            Node<Integer> current = head;
            while (current != tail) {
                stringBuilder.append(current.getValue()).append(", ");
                current = current.getNext();
            }
            // 追加尾节点
            stringBuilder.append(current.getValue()).append(" }}");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) throws Exception {
        LinkedListStack linkedListStack = new LinkedListStack();
        linkedListStack.push(1);
        linkedListStack.push(2);
        linkedListStack.push(3);
        linkedListStack.push(4);
        System.out.println(linkedListStack);
        Integer pop1 = linkedListStack.pop();
        System.out.println(pop1);
        Integer pop2 = linkedListStack.pop();
        System.out.println(pop2);
        Integer pop3 = linkedListStack.pop();
        System.out.println(pop3);
        System.out.println(linkedListStack);
    }
}
